package top.minuy.subject.leetcode.lcp04;

import java.util.*;

/**
 * 最大流二分图最大匹配
 * LCP 04. 覆盖
 * 你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠地覆盖在完好的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。
 * <p>
 * <p>
 * <p>
 * 输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。
 * <p>
 * 输出：一个整数，代表最多能在棋盘上放的骨牌数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2, m = 3, broken = [[1, 0], [1, 1]]
 * 输出：2
 * 解释：我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * 输入：n = 3, m = 3, broken = []
 * 输出：4
 * 解释：下图是其中一种可行的摆放方式
 * <p>
 * <p>
 * <p>
 * <p>
 * 限制：
 * <p>
 * 1 <= n <= 8
 * 1 <= m <= 8
 * 0 <= b <= n * m
 * 通过次数2,704提交次数7,113
 *
 * @author Minuy
 * @time 21:54
 * @date 2021/11/29
 */
public class Solution {
    public int domino(int n, int m, int[][] broken) {

        // 构建整个棋盘，1为坏掉的
        int[][] board = new int[n][m];
        for (int[] ints : broken) {
            board[ints[0]][ints[1]] = 1;
        }

        // 创建图
        WeightedGraphDynamic wgd = new WeightedGraphDynamic();

        // 添加顶点
        int v = m * n;
        for (int i = 0; i < v; i++) {
            wgd.addVertex(i);
        }

        // 遍历所有格子
        for (int i = 0; i < n; i++) { // 行
            for (int j = 0; j < m; j++) { // 列
                if (board[i][j] == 0) { // 好格子
                    // 右格子是否相连
                    if (j + 1 < m && board[i][j + 1] == 0) {
                        wgd.addEdge((i * m) + j, (i * m) + (j + 1), 0);
                    }
                    // 下格子是否相连
                    if (i + 1 < n && board[i + 1][j] == 0) {
                        wgd.addEdge((i * m) + j, ((i + 1) * m) + j, 0);
                    }
                }
            }
        }

        // 二分图最大流最大匹配算法
        return new BipartiteMatching(wgd).maxMatching();
    }


    /**
     * 检测二分图，深度优先遍历
     *
     * @author Minuy
     * @time 20:21
     * @date 2021/11/19
     */
    public class BipartitionDetection {
        public static final boolean BLUE = true;  // 蓝色
        public static final boolean GREEN = false;  // 绿色

        private WeightedGraphDynamic g;
        private boolean[] isVisited;
        private boolean[] colors;
        private boolean isBipartition = true;

        public BipartitionDetection(WeightedGraphDynamic g) {
            this.g = g;

            if (g.isDirected()) {
                throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
            }

            this.isVisited = new boolean[g.V()];

            this.colors = new boolean[g.V()];

            // 遍历所有联通分量
            for (int v = 0; v < g.V(); v++) {
                if (!isVisited[v]) {
                    // 默认给蓝色
                    if (!dfs(v, BLUE)) { // 不是二分图
                        isBipartition = false;
                        break;
                    }
                }
            }
        }

        /**
         * 判断点是否是蓝色的
         *
         * @param v 要被判断的顶点
         * @return boolean
         * @author Minuy
         * @date 2021/11/29 21:18
         */
        public boolean isBlue(int v) {
            g.validateVertex(v);
            return colors[v] == BLUE;
        }

        private boolean dfs(int v, boolean color) {
            isVisited[v] = true;

            colors[v] = color;

            for (String ws : g.adj(v)) {
                int w = Integer.parseInt(ws);
                if (!isVisited[w]) { // 如果没访问过
                    // 染色
                    if (colors[v] == GREEN) {
                        dfs(w, BLUE);
                    } else if (colors[v] == BLUE) {
                        dfs(w, GREEN);
                    }
                } else if (isVisited[w]) { // 如果访问过了，检测冲突
                    if (colors[v] == colors[w]) { // 冲突
                        return false;
                    }
                }
                // 有冗余的检测，没被访问过的是在本节点去赋值的，
                // 所以一定不是冲突的，这里应该是只检测访问过的
            }
            return true;
        }

        /**
         * 给出本图是否是二分图
         *
         * @return boolean 是否是二分图
         * @author Minuy
         * @date 2021/11/19 20:51
         */
        public boolean isBipartition() {
            return isBipartition;
        }
    }


    /**
     * 最大流二分图匹配
     *
     * @author Minuy
     * @time 20:59
     * @date 2021/11/29
     */
    public class BipartiteMatching {
        private WeightedGraphDynamic g;
        private int s, t;
        private int maxMatching;

        public BipartiteMatching(WeightedGraphDynamic g) {
            this.g = g;

            if (g.isDirected()) {
                throw new IllegalArgumentException("BipartiteMatching only works in undirected graph.");
            }

            BipartitionDetection bd = new BipartitionDetection(g);
            if (!bd.isBipartition()) {
                throw new IllegalArgumentException("BipartiteMatching only works for bipartite graph.");
            }

            // 创建最大流网络
            WeightedGraphDynamic wgd = createNetWork(bd);

            // 计算最大匹配
            MaxFlowDynamic mfd = new MaxFlowDynamic(wgd, s, t);
            maxMatching = mfd.maxFlow();
        }

        private WeightedGraphDynamic createNetWork(BipartitionDetection bd) {
            WeightedGraphDynamic wgd = new WeightedGraphDynamic(true);

            // 添加顶点
            for (int v = 0; v < g.V(); v++) {
                wgd.addVertex(v);
            }
            s = g.V();
            t = s + 1;
            wgd.addVertex(s);
            wgd.addVertex(t);

            // 蓝 -> 绿
            for (int v = 0; v < g.V(); v++) {
                if (bd.isBlue(v)) {
                    wgd.addEdge(s, v, 1);
                } else {
                    wgd.addEdge(v, t, 1);
                }
                for (String ws : g.adj(v)) {
                    int w = Integer.parseInt(ws);
                    if (w < v) { // 不存在等于w==v的情况，这样可以过滤掉一般的无向图“边”
                        if (bd.isBlue(v)) {
                            wgd.addEdge(v, w, 1);
                        } else {
                            wgd.addEdge(w, v, 1);
                        }
                    }
                }
            }

            return wgd;
        }

        /**
         * 获取最大匹配
         *
         * @return int 最大匹配
         * @author Minuy
         * @date 2021/11/29 21:37
         */
        public int maxMatching() {
            return maxMatching;
        }
    }


    /**
     * 网络中的最大流
     * Ford-Fulkerson 思想
     * Edmonds-Karp 算法
     * 改用WeightedGraphDynamic图类
     *
     * @author Minuy
     * @time 21:32
     * @date 2021/11/28
     */
    public class MaxFlowDynamic {
        private WeightedGraphDynamic rg; // 残量图
        private WeightedGraphDynamic g; // 要处理的图
        private int s, t; // 流源点和流终点
        private int maxFlow; // 最大流

        public MaxFlowDynamic(WeightedGraphDynamic g, int s, int t) {
            this.g = g;
            if (!g.isDirected()) {
                throw new IllegalArgumentException("MaxFlow only works in directed graph.");
            }

            g.validateVertex(s);
            g.validateVertex(t);
            if (s == t) {
                throw new IllegalArgumentException("The s and the t should be different.");
            }
            this.s = s;
            this.t = t;

            rg = creatResidualGraph();
            maxFlow = 0;

            while (true) {
                // 找一条增广路径
                List<Integer> augPath = getAugmentingPath();
                if (augPath.size() == 0) { // 如果不能找到路径了
                    break; // 结束
                }
                // 找出路径中的最小值
                int minFlow = rg.getWeight(augPath.get(0), augPath.get(1));
                for (int i = 1; i < augPath.size(); i++) {
                    minFlow = Math.min(rg.getWeight(augPath.get(i - 1), augPath.get(i)), minFlow);
                }

                //更新最大流数据
                maxFlow += minFlow;

                // 更新残量图
                for (int i = 1; i < augPath.size(); i++) {
                    int v = augPath.get(i - 1);
                    int w = augPath.get(i);
                    rg.setWeight(v, w, rg.getWeight(v, w) - minFlow);
                    rg.setWeight(w, v, rg.getWeight(w, v) + minFlow);
                }
            }

        }

        /**
         * 获取计算出的最大流量
         *
         * @return int 最大流量
         * @author Minuy
         * @date 2021/11/29 14:10
         */
        public int maxFlow() {
            return maxFlow;
        }

        /**
         * 得到增广路径
         *
         * @return List<Integer> 返回一条曾广路径
         * @author Minuy
         * @date 2021/11/29 13:32
         */
        private List<Integer> getAugmentingPath() {
            int[] pre = new int[rg.V()];
            Arrays.fill(pre, -1);

            ArrayList<Integer> queue = new ArrayList<>();
            int v = s;
            queue.add(v);
            pre[v] = v;
            while (!queue.isEmpty()) {
                v = queue.remove(0);

                if (v == t) { // 到目标点了可以提前结束
                    break;
                }

                for (String ws : rg.adj(v)) {
                    int w = Integer.parseInt(ws);
                    if (pre[w] == -1) { // 如果顶点在本次遍历中未被访问
                        if (rg.getWeight(v, ws) > 0) { // 这条路还有 残量/流量
                            queue.add(w);
                            pre[w] = v;
                        }
                    }
                }
            }

            List<Integer> path = new ArrayList<>();

            if (pre[t] != -1) { // 如果到过了目的地
                // 找出路径
                int cur = t;
                while (cur != s) {
                    path.add(cur);
                    cur = pre[cur];
                }
                path.add(s);

                Collections.reverse(path);
            }

            return path;
        }

        /**
         * 创建残量图
         *
         * @return WeightedGraphDynamic 残量图
         * @author Minuy
         * @date 2021/11/29 14:11
         */
        private WeightedGraphDynamic creatResidualGraph() {
            WeightedGraphDynamic rg = new WeightedGraphDynamic(true);

            // 复制顶点
            for (int v = 0; v < g.V(); v++) {
                rg.addVertex(v);
            }

            // 复制边，构建 流量/残量
            for (int v = 0; v < g.V(); v++) {
                for (String w : g.adj(v)) {
                    if (rg.hasEdge(v, w) || rg.hasEdge(w, v)) {
                        throw new IllegalArgumentException("Parallel edge or cycle has detection.");
                    } else {
                        // v -> w
                        int residual = g.getWeight(v, w); // 残量，剩余的容量
                        int flow = 0; // 流量，已经使用的容量

                        rg.addEdge(v, w, residual);
                        rg.addEdge(w, v, flow);
                    }
                }
            }

            return rg;
        }

    }

    /**
     * 带权图
     * 正式在后面的例子中使用的图的表示类 简单图
     * 使用基于红黑树的邻接表实现
     * V0.2
     * 带方向
     * V0.3动态的增加，删除边，增加，删除点，使用字符串作为顶点名称标记
     *
     * @author Minuy
     * @time 0:15
     * @date 2021/11/27
     */
    public class WeightedGraphDynamic{
        private int V; // 顶点个数
        private int E; // 边的条数
        private Map<String, Map<String, Integer>> adj; // 邻接表，（顶点名，邻接表（邻边顶点名，权值））
        private boolean isDirected; // 是否有向

        /**
         * 创建一个空无向有权图
         *
         * @author Minuy
         * @date 2021/11/28 16:50
         */
        public WeightedGraphDynamic() {
            this(false);
        }

        /**
         * 构造函数，从文件构造一个有权图
         *
         * @param isDirected 指定是否有向
         * @author Minuy
         * @date 2021/11/28 16:51
         */
        public WeightedGraphDynamic(boolean isDirected) {
            // 创建邻接表
            adj = new HashMap<>();
            this.isDirected = isDirected;
        }

        /**
         * 添加一个顶点到图中
         *
         * @param v 要添加顶点的ID
         * @author Minuy
         * @date 2021/11/28 9:27
         */
        public void addVertex(int v) {
            addVertex(String.valueOf(v));
        }

        /**
         * 添加一个顶点到图中
         *
         * @param v 要添加顶点的名字
         * @author Minuy
         * @date 2021/11/28 9:28
         */
        public void addVertex(String v) {
            adj.put(v, new HashMap<>());
            V++;
        }

        /**
         * 添加一条边
         *
         * @param v      开始顶点
         * @param w      结束顶点
         * @param weight 权
         * @author Minuy
         * @date 2021/11/28 10:31
         */
        public void addEdge(int v, int w, int weight) {
            addEdge(String.valueOf(v), String.valueOf(w), weight);
        }

        /**
         * 添加一条边
         *
         * @param v      开始顶点
         * @param w      结束顶点
         * @param weight 权
         * @author Minuy
         * @date 2021/11/28 16:49
         */
        public void addEdge(int v, String w, int weight) {
            addEdge(String.valueOf(v), w, weight);
        }

        /**
         * 添加一条边
         *
         * @param v      开始顶点
         * @param w      结束顶点
         * @param weight 权
         * @author Minuy
         * @date 2021/11/28 16:50
         */
        public void addEdge(String v, int w, int weight) {
            addEdge(v, String.valueOf(w), weight);
        }

        /**
         * 添加一条边
         *
         * @param v      开始顶点
         * @param w      结束顶点
         * @param weight 权
         * @author Minuy
         * @date 2021/11/28 10:32
         */
        public void addEdge(String v, String w, int weight) {
            validateVertex(v);
            validateVertex(w);

            if (v.equals(w)) {
                // 自环，不允许出现在简单图中
                throw new IllegalArgumentException("Self Loop is Detected!");
            }

            if (adj.get(v).containsKey(w)) {
                // 平行边，不允许出现在简单图中
                // 若其他地方需要用到平行边，一般我们保留最小的那个平行边的权值，
                // 也可当做没有平行边来处理
                throw new IllegalArgumentException("Parallel Edges are Detected!");
            }

            adj.get(v).put(w, weight); // 连接两个顶点
            if (!isDirected()) {// 有向图维护度
                adj.get(w).put(v, weight); // 无向图的表示是两边都相连的
            }

            // 维护E
            E++;
        }


        /**
         * 验证顶点序号的合法性
         *
         * @param v 顶点值
         * @author Minuy
         * @date 2021/11/15 17:26
         */
        public void validateVertex(int v) {
            validateVertex(String.valueOf(v));
        }

        /**
         * 验证顶点序号的合法性
         *
         * @param v 顶点值
         * @author Minuy
         * @date 2021/11/28 10:26
         */
        public void validateVertex(String v) {
            if (!adj.containsKey(v)) {
                throw new IllegalArgumentException("The graph not has vertex " + v + ".");
            }
        }

        /**
         * 只读，边的数量
         *
         * @return int 边的数量
         * @author Minuy
         * @date 2021/11/15 17:35
         */
        public int E() {
            return E;
        }

        /**
         * 只读，顶点的数量
         *
         * @return int 顶点的数量
         * @author Minuy
         * @date 2021/11/15 17:35
         */
        public int V() {
            return V;
        }

        /**
         * 验证两个顶点之间是否有变
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/28 10:26
         */
        public boolean hasEdge(String v, String w) {
            validateVertex(v);
            validateVertex(w);
            return adj.get(v).containsKey(w);
        }

        /**
         * 验证两个顶点之间是否有变
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/15 17:38
         */
        public boolean hasEdge(int v, int w) {
            return hasEdge(String.valueOf(v), String.valueOf(w));
        }

        /**
         * 验证两个顶点之间是否有变
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/28 16:35
         */
        public boolean hasEdge(String v, int w) {
            return hasEdge(v, String.valueOf(w));
        }

        /**
         * 验证两个顶点之间是否有变
         *
         * @param v 顶点1的序号
         * @param w 顶点2的序号
         * @return boolean 有无边
         * @author Minuy
         * @date 2021/11/28 16:36
         */
        public boolean hasEdge(int v, String w) {
            return hasEdge(String.valueOf(v), w);
        }

        /**
         * 返回与顶点v相邻的所有顶点
         *
         * @param v 顶点v
         * @return Iterable<String> 与顶点v相邻的所有顶点
         * @author Minuy
         * @date 2021/11/15 19:55
         */
        public Iterable<String> adj(int v) {
            return adj(String.valueOf(v));
        }

        /**
         * 返回顶点v的邻接顶点
         *
         * @param v 顶点v
         * @return Iterable<String> 顶点v的邻接顶点
         * @author Minuy
         * @date 2021/11/28 16:29
         */
        public Iterable<String> adj(String v) {
            validateVertex(v);
            return adj.get(v).keySet();
        }

        /**
         * 重新设置边的权值
         *
         * @param v      顶点v，边的起点
         * @param w      顶点v，边的终点
         * @param weight 新的权值
         * @author Minuy
         * @date 2021/11/28 16:58
         */
        public void setWeight(int v, int w, int weight) {
            setWeight(String.valueOf(v), String.valueOf(w), weight);
        }

        /**
         * 重新设置边的权值
         *
         * @param v      顶点v，边的起点
         * @param w      顶点v，边的终点
         * @param weight 新的权值
         * @author Minuy
         * @date 2021/11/28 16:57
         */
        public void setWeight(String v, String w, int weight) {
            hasEdge(v, w);
            adj.get(v).put(w, weight);
            if (!isDirected()) {
                adj.get(w).put(v, weight);
            }
        }

        /**
         * 获取一条边的权值
         *
         * @param v 边的一端顶点
         * @param w 边的另一端顶点
         * @return int 这条边的权值
         * @author Minuy
         * @date 2021/11/25 9:31
         */
        public int getWeight(int v, int w) {
            return getWeight(String.valueOf(v), String.valueOf(w));
        }

        /**
         * 获取一条边的权值
         *
         * @param v 边的一端顶点
         * @param w 边的另一端顶点
         * @return int 这条边的权值
         * @author Minuy
         * @date 2021/11/28 16:59
         */
        public int getWeight(String v, int w) {
            return getWeight(v, String.valueOf(w));
        }

        /**
         * 获取一条边的权值
         *
         * @param v 边的一端顶点
         * @param w 边的另一端顶点
         * @return int 这条边的权值
         * @author Minuy
         * @date 2021/11/28 16:59
         */
        public int getWeight(int v, String w) {
            return getWeight(String.valueOf(v), w);
        }

        /**
         * 获取一条边的权值
         *
         * @param v 边的一端顶点
         * @param w 边的另一端顶点
         * @return int 这条边的权值
         * @author Minuy
         * @date 2021/11/28 10:30
         */
        public int getWeight(String v, String w) {
            if (hasEdge(v, w)) {
                return adj.get(v).get(w);
            }
            throw new IllegalArgumentException(String.format("Not has edge %s-%s.", v, w));
        }

        /**
         * 查询图是有向的还是无向的
         *
         * @return boolean 图的方向性
         * @author Minuy
         * @date 2021/11/27 9:08
         */
        public boolean isDirected() {
            return isDirected;
        }
    }

}
